package experiment3.dijkstra;


import java.util.Random;
import java.util.Scanner;

import static util.Util.generateRandomArray;

public class Dijkstra {
    public static Long INF = Long.MAX_VALUE;
    Long[] distance;
    int[] parent;
    boolean[] visit;

    public void solution(Long[][] array) {
        //保存到顶点i的最短路径
        distance = new Long[array.length];
        //保存顶点i的访问状态
        visit = new boolean[array.length];
        //记录路径，节点i的父节点是parent[i]
        parent = new int[array.length];
        //初始化
        for (int i = 0; i < array.length; i++) {
            distance[i] = INF;
            visit[i] = false;
            parent[i] = -1;
        }

        int visitNode = 0;
        Long minDis = 0L;
        for (int i = 0; i < array.length; i++) {
            visit[visitNode] = true;
            int min = 0;
            for (int j = 0; j < array.length; j++) {
                if (!visit[j] && array[visitNode][j] + minDis < distance[j]) {
                    distance[j] = array[visitNode][j] + minDis;
                    parent[j] = visitNode;
                }
                if (!visit[j] && distance[j] < distance[min]) {
                    min = j;
                }
            }
            minDis = distance[min];
            visitNode = min;
        }
    }

    public void printPath(int end) {
        StringBuilder sb = new StringBuilder();

        while (true) {
            sb.insert(0, end);
            if (parent[end] == -1) {
                break;
            }
            sb.insert(0, "->");
            end = parent[end];
        }
        System.out.println(sb.toString());
    }

    public String minDistance(int i) {
        return (distance[i] == Long.MAX_VALUE || distance[i] < 0) ? "INF" : distance[i].toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        Long[][] array = generateRandomArray(scanner.nextInt());
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length; j++) {
                System.out.print(array[i][j] + "   ");
            }
        }
        System.out.println();

        Dijkstra myDijkstra = new Dijkstra();
        myDijkstra.solution(array);
        int end = array.length;
        for (int i = 0; i < end; i++) {
            myDijkstra.printPath(i);
            System.out.println("0到" + i + "的最短距离为:" + myDijkstra.minDistance(i));
            System.out.println();
        }
    }



}
